package topo;

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;
import java.util.Vector;


import util.CombinationGenerator;
import util.IOTopology;

public class ScaleFreeNetwork {
	
	private static ScaleFreeNetwork instance = new ScaleFreeNetwork(); 
	
	public static ScaleFreeNetwork instance(){
		return instance;
	}
	
	private ScaleFreeNetwork(){
		mRandom = new Random(System.currentTimeMillis());
	}

	private Random mRandom ;
	private Vector<Node> node_index ;

	public Topology createScaleFreeNet(int initNumNodes,
			int numEdgesToAttach, int numTimeSteps) {
	
		int mSteps = 0;
		Topology graph = new Topology();
		graph.setLabel("Scale-Free");

		if (initNumNodes < 1)
			return null;
		// initial fully connected graph
		 node_index = new Vector<Node>();
		for (int i = 0; i < initNumNodes; i++) {
			Node node = new Node();
			graph.addNode(node);
			node_index.add(node);
		}
		CombinationGenerator comb = new CombinationGenerator(initNumNodes, 2);
		int combItems[];
		while (comb.hasMore()) {
			combItems = comb.getNext();
			if (combItems.length != 2) {
				System.err.println("Incorrect number of combination length : "
						+ combItems.length);
				return null;
			}
			Node node1 = graph.getNodes().get(combItems[0]);
			Node node2 = graph.getNodes().get(combItems[1]);
			Edge edge = new Edge(node1, node2);
			graph.addEdge(edge);
		}

		List<Edge> edges = new LinkedList<Edge>();

		for (int i = 0; i < numTimeSteps; i++) {
			Node newNode = new Node();
			graph.addNode(newNode);
			mSteps++;
			for (int j = 0; j < numEdgesToAttach; j++) {
				Edge edge = createRandomEdge(node_index, newNode, graph);
				if (isInEdgeList(edges, edge))
					j--;
				else
					edges.add(edge);
			}

			for (Iterator<Edge> iter = edges.iterator(); iter.hasNext();) {
				graph.addEdge((Edge) iter.next());
			}
			node_index.add(newNode);

		}
		//System.out.println(" number of nodes : " + graph.getNodes().size());
		//System.out.println(" number of edges : " + graph.getEdges().size());
		return graph;
	}

	public Edge createRandomEdge(Vector<Node> nodes, Node newNode,
			Topology graph) {

		Node attach_point;
		double attach_prob;
		do {
			int randInt = mRandom.nextInt(nodes.size());
		//	System.out.println(" randInt : " + randInt);
			attach_point = nodes.elementAt(randInt);
			attach_prob = (double) (graph.getNodeOutDegree(attach_point) + 1)
					/ (double) ((graph.getEdges().size() + graph.getNodes()
							.size()) - 1);
		} while (mRandom.nextDouble() > attach_prob);
		return new Edge(newNode, attach_point);

	}

	private boolean isInEdgeList(List<Edge> list, Edge edge) {

		for (Iterator<Edge> iterator = list.listIterator(); iterator.hasNext();) {
			Edge list_edge = iterator.next();
			if (list_edge.getFrom().equals(edge.getFrom())
					&& list_edge.getTo().equals(edge.getTo()))
				return true;
			else if (list_edge.getFrom().equals(edge.getTo())
					&& list_edge.getTo().equals(edge.getFrom()))
				return true;
		}
		return false;
	}

	public static void main(String[] args) {
		ScaleFreeNetwork sfn = new ScaleFreeNetwork();
		Topology topo = sfn.createScaleFreeNet(4, 4, 100-4);
		IOTopology.exportTopologyFile(topo, "topology_2.txt");
	}
}
